package acwing_02;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;

public class _154_单调队列_滑动窗口 {
	public static void main(String[] args) {
		// 由于输出太占时间导致Time Limit Exceeded 所以将值进行拼接最后再输出达到Accepted
		StringBuilder minStr = new StringBuilder();
		StringBuilder maxStr = new StringBuilder();
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int k = scan.nextInt();
		// 双向队列
		Deque<Integer> q = new ArrayDeque<>();
		int arr[] = new int[n];
		for(int i = 0; i < n; i++) {
			arr[i] = scan.nextInt();
		}
		
		// 算最小值
		for(int i = 0; i < n; i++) {
			// 头元素存储的下标小于窗口范围最小下标，则需要移除该头元素
			if(!q.isEmpty() && q.getFirst() < i - k + 1) {
 				q.pollFirst();
			}
			// 尾元素存储的下标得到的元素值比新元素大，则需要弹出尾元素
			while(!q.isEmpty() && arr[q.getLast()] >= arr[i]){
				q.pollLast();
			}
			// 加入新元素的下标
			q.addLast(i);
			
			// 由于有k个元素作为窗口 数组下标从0开始，因此当i = k-1时，才出现第一个窗口
			if(i >= k - 1) {
				minStr.append(arr[q.getFirst()] + " ");
			}
		}
				
		// 算最大值，与最小值同理，只是把 >= 换成 <=
		q = new ArrayDeque<>();
		for(int i = 0; i < n; i++) {
			if(!q.isEmpty() && q.getFirst() < i - k + 1) {
 				q.pollFirst();
			}
			while(!q.isEmpty() && arr[q.getLast()] <= arr[i]){
				q.pollLast();
			}
			q.addLast(i);
			
			if(i >= k - 1) {
				maxStr.append(arr[q.getFirst()] + " ");
			}
		}
		
		System.out.println(minStr.toString());
		System.out.println(maxStr.toString());
		scan.close();
		
	}
}
